＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　　　　　　 ■■■■
　　　　　■　　　　■　　　　　　　■　　　　　　　　■
　　　　　■　　　　　　　　　　　■■■　　　　　　■■■
　　　　　■　　　　■　　　　　　　■　　　　　　　　■
　　　　　　 ■■■■
               〜基礎から　★　Ｃ＋＋Ｐｒｏｇｒａｍｉｎｇ〜
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　　【注意】　このマガジンは、最大化してお読みください。
　　　　　　　また、等角フォントでお読みください。
　　　　　　　　　　（ＭＳ　ゴシックなど）

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　発行者　　　　　　むーくん
　マガジンＮＯ．　　アルゴリズム編No.41 連立方程式の解法
　発行日　　　　　　02/08/07
　講読人数　　　　　３８００名ぐらい
　マガジンＩＤ　　　0000050494
　　　　　　　　　　このマガジンは、まぐまぐから配信されています。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★あいさつ★

お久しぶりです。
TVチューナー・ビデオキャプチャーを購入しまして、
テレビ見ながらPCいじってます。

そのときに、テレビの信号を２分する加工をやりまして、
久しぶりに工作しました。
同軸ケーブル剥いたりするのもたまには楽しいですねぇ。
電子工作でも始めようかなぁ、とか思ってみたり（笑）。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★目次★

　　　・連立方程式
　　　・解法の種類
　　　・参考（解空間について）
　　　・注意１
　　　・注意２
　　　・今日のポイント
　　　・予告

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★連立方程式★

コンピュータでの科学技術計算は
連立方程式や行列が一番多いと言われており、
代表的なアルゴリズムが山ほど存在します。

ところが、人間にはよく使われる考え方も、コンピュータには
適さないことがあります。

例えば、下のような方程式を解いてみましょう。

　｛ 4x + 3y = 5　・・・ I
　｛  x + 3y = 17 ・・・ II

まず、IIを移項して 3y = 17 - x とします。
これをIに代入すると

　　4x + 17 - x = 5　となるので、同類項にまとめてみます。

　　3x = -12 より、 x = -4 、これをIIの移項した式に代入し、

　　3y = 17 - (-4) = 21　、よって

　　y = 7

こうして(x,y) = (-4,7)と解くことができました。


これは代入法といいます。
このような考え方は、コンピュータには適しません。
なぜなら、代入の仕方や、移項の仕方が複数パターンあるからです。

コンピュータが解けるようにするには、
常にアルゴリズムが一意に決まるようなやりかたを考える必要があります。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★解法の種類★

実際には、

　　・掃き出し法

　　・ガウス・ザイデル法

　　・行列を用いた解法（逆行列を掛ける）

などが知られています。

次回から、実際のアルゴリズムを勉強していきましょう。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★参考（解空間について）

連立方程式ではxやyなどの変数を「元」と言っています。
元がn個で、元の最大次数が1ならば、「n元1次連立方程式」といいます。

このマガジンでは「n元1次連立方程式」のみについて考えていきます。

　＃2次以上になると複雑すぎるからです

また、n元の連立方程式では、方程式がn本以上必要です。
そうでないと、解が１点に決まりません。
例を挙げて説明します。


極端な例では、

　｛ x + y = 3

という連立方程式（１本しかありませんが ^^;)を考えてみます。
これは、2元連立方程式で、式は1本であることを確認してください。

この場合、x=1,y=2 、 x=6,y=-3 、x=500,y=-497など
いくらでも考えられます。

実は、y = -x + 3と同じ式なので、これを満たす解は直線上にあるのです。

　＃ y = ax + bは一次関数ですよね

この場合、「2」元の式が「1」本の式に拘束されて「2-1」次元、
つまり『「1」次元の解を持った』と解釈することができます。
これを解空間と呼びます。


同様に、5元の方程式が2本の式で表記された場合、
解空間は、5-2で３次元になります。


逆に(x,y,z)=(1,4,9)のように、解が１点で示される場合は
解空間が０次元のときだと言ってもいい訳です。

n次元に対して、式がn本のとき、n-n=0なので０次元ですよね。
だから、解が１点になり、「解けた」と言えるのです。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★注意１★

でも、こういうのはダメですよ。
一見、2元の方程式に対して式が2本あるように見えます。
解が１点に決まるように見えるでしょう？

　｛  x +  y = 1　・・・ I
　｛ 2x + 2y = 2　・・・ II

これは、Iを2倍したらIIと等しくなります。
IとIIは全く等価なことを言っているので、
式は1本あるとしか見なされません。

だから、解空間はやはり１次元で、解は１点に決まりません。


また、下のようなのもダメです。

　｛ x + y = 1　・・・ I
　｛ x + y = 2　・・・ II

これって、絶対に解があるわけありませんよね。
Iでは「xとyを足すと1だ」、IIでは「xとyを足すと2だ」と
言ってることが矛盾してますから、ダメに決まってます。

こういうのは「不能な連立方程式」といって、解は存在しません。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★注意２★

斉次連立方程式というのがあります。

｛ ax + by + cz = 0
｛ dx + ey + fz = 0
｛ gx + hy + iz = 0

という形で、要は定数の部分が全てゼロの連立方程式です。

これは、必ず、(x,y,z)=(0,0,0)という解を持ちます。
x,y,zそれぞれ全部に0を代入すれば0が求まるので分かると思います。

これを「自明な解」といい、必ず存在します。

係数の条件により、自明な解以外の解を持つことも、
持たないこともあるので厄介です。


これから作成していくプログラムは、解空間が０次元のとき、
つまり解が１点に決まる場合だけを考えます。

プログラムをテストするとき、こういうのにハマらないでくださいね。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★今日のポイント★

　　・科学技術計算では、連立方程式を解くことはよく用いられる

　　・人間の解き方と、コンピュータの解き方は
　　　区別して考える必要がある

　　・解が１点に決まるには、元の個数と同等の式の本数が必要

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★予告★

　　　掃き出し法を学習します

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

講読解除はこちら
http://web1.freecom.ne.jp/~mu-home/mmg/cpp.html

バックナンバーはこちら
http://web1.freecom.ne.jp/~mu-home/mmg/cpp.html

内容について質問やご意見など
smukun.com

筆者のホームページ（むーくんの理学的なんでも講座）
http://www.hello.sh/nandemo/

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊